package com.algorithm.learning.binarysearch;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/17 21:20
 **/
public class X的平方根 {

    public static void main(String[] args) {
        X的平方根 x的平方根 = new X的平方根();
        System.out.println(x的平方根.mySqrt(15));
    }

    /**
     * 给你一个非负整数 x ，计算并返回x的算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     *
     * 输入：x = 4
     * 输出：2
     *
     * 输入：x = 8
     * 输出：2
     * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int left = 1;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (mid > x / mid) {
                // 这里说明 mid * mid > x，那么区间就是[left, mid - 1]
                right = mid - 1;
            } else {
                // 这里说明 mid * mid < x，那么区间就是[mid, right]
                left = mid;
            }
        }
        return left;
    }


}
